1. Field of the Invention
This invention relates to computer systems, and more particularly to an improved non-restoring division method and apparatus.
2. Description of the Related Art
Division is one of the more complex and lengthy operations performed in a digital processor. Many steps or iterations are needed--usually one iteration for each bit in the dividend. Like long division practiced by many school-children, the divisor is subtracted from a partial remainder during each iteration. Binary arithmetic allows for non-restoring division to be used, where the partial remainder at any iteration is allowed to be negative as well as positive. Should the partial remainder be negative, then too large a number was subtracted. Restoring division would immediately add the divisor back to the partial remainder to restore the partial remainder to a positive number. However, non-restoring division skips this restore step.
For non-restoring division, on the iteration following a negative partial remainder, the divisor is added instead of subtracted. Since the divisor is effectively shifted to the right for each successive iteration, and in binary arithmetic each shift reduces the divisor by half (a right shift multiplies by 2.sup.-1 or 1/2), adding the divisor instead of subtracting is equivalent to not subtracting the divisor in the previous iteration (which would produce the negative remainder) and subtracting the divisor in the current iteration.
For example, suppose the divisor is 5, and the first iteration should not have subtracted five (-5), while the next iteration should subtract five, right-shifted, or half of five (-(1/2)*5). Instead, the next iteration adds the shifted five (+(1/2)*5) because the first iteration subtracted too much, producing a negative partial remainder. Adding five in the second step has the effect: -5.sub.First Iter. +(1/2)*5.sub.Second Iter. =-(1/2)*5. Restoring division would require an extra restore step: -5.sub.First Iter. +5.sub.Restore -(1/2)*5.sub.Second Iter. =-(1/2)*5. Non-restoring division reduces the number of steps required in a division operation because each of the partial remainders do not have to be restored to positive numbers. Instead, the correction is made in the next iteration by adding instead of subtracting.
While non-restoring division is well-known and often implemented, detection of overflow conditions may require additional steps, especially when both signed and unsigned division are to be performed. Often additional steps at the beginning or end of a division operation are used to test or determine if an overflow will or has occurred. Additionally, the dividend may be either the same width (n-bits) as the divisor, quotient, and remainder, or the dividend may be twice the width (2n-bits). The dividend and the divisor are usually converted to positive numbers in separate steps before the division is performed, and two separate final restore steps after the division finishes are used to ensure that the final remainder is positive.
What is desired is an apparatus to detect overflow and perform division in fewer steps and in a simpler fashion than in prior systems, and an apparatus to detect overflow for both signed and unsigned division without extra steps. It is also desired to have a division apparatus that can operate on both n-bit and 2n-bit dividends.